package code1_100.code81_90;

/**
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 *
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 */
public class _86partition {

    /**
     * 思考 ： 第一种方法，直接遍历进行重建。
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 37.7 MB     * , 在所有 Java 提交中击败了     * 71.67%     * 的用户
     * @param head
     * @param x
     * @return
     */
    public static ListNode partition(ListNode head, int x) {
        ListNode listNode1 = new ListNode(0);
        ListNode listNode2 = new ListNode(0);

        ListNode temp;
        ListNode node1 = listNode1;
        ListNode node2 = listNode2;

        ListNode headTemp = head;
        while (headTemp!=null){
            if(headTemp.val<x){
                temp = new ListNode(headTemp.val);
                node1.next = temp;
                node1 = temp;
            }else {
                temp = new ListNode(headTemp.val);
                node2.next = temp;
                node2 = temp;
            }
            headTemp = headTemp.next;
        }
        node1.next = listNode2.next;
        return listNode1.next;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1,new ListNode(4,new ListNode(3,new ListNode(2,new ListNode(5,new ListNode(2))))));
        System.out.println(partition(node,3).val);
    }

}
